import java.util.ArrayList;
import java.util.List;

public class WeightedGraph<V> extends AbstractGraph<V> {
    /**
     * 构造方法
     */
    public WeightedGraph() {
    }

    public WeightedGraph(V[] vertices, int[][] edges) {
        createWeightedGraph(vertices, edges);
    }

    public WeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        createWeightedGraph(vertices, edges);
    }

    /**
     * 构建顶点线性表和邻接边线性表
     */
    public void createWeightedGraph(V[] vertices, int[][] edges) {
        for (int i = 0; i < vertices.length; i++) {
            addVertex(vertices[i]);
        }

        for (int i = 0; i < edges.length; i++) {
            addEdge(edges[i][0], edges[i][1], edges[i][2]);
        }
    }

    public void createWeightedGraph(List<V> vertices, List<WeightedEdge> edges) {
        for (int i = 0; i < vertices.size(); i++) {
            addVertex(vertices.get(i));
        }

        for (int i = 0; i < edges.size(); i++) {
            addEdge(edges.get(i));
        }
    }

    /**
     * 得到指定边的权重
     */
    public double getWeight(int u, int v) throws Exception {
        for (Edge e : neighbors.get(u)) {
            if (e.v == v) {
                return ((WeightedEdge) e).weight;
            }
        }

        throw new Exception("Edge doesn't exist!");
    }

    /**
     * 打印有权边
     */
    public void printWeightedEdge() {

        for (int i = 0; i < vertices.size(); i++) {
            System.out.print(vertices.get(i) + "(" + i + "):");
            for (Edge e : neighbors.get(i)) {
                System.out.print("(" + e.u + "," + e.v + "," +
                        ((WeightedEdge) e).weight + ") ");
            }
            System.out.println();
        }
    }

    /**
     * 增加一条有权边
     */
    public boolean addEdge(int u, int v, double weight) {
        return addEdge(new WeightedEdge(u, v, weight));
    }

    public boolean addEdge(WeightedEdge e) {
        if (e.u < 0 || e.u > vertices.size() - 1) throw new IllegalArgumentException("no such index:" + e.u);
        if (e.v < 0 || e.v > vertices.size() - 1) throw new IllegalArgumentException("no such index:" + e.v);
        if (e.weight < 0) throw new IllegalArgumentException("no such weight:" + e.weight);
        if (neighbors.get(e.u).contains(e)) {
            return false;
        } else {
            int key = 0;
            for (Edge edge : neighbors.get(e.u)) {
                if (edge.equals(e)) {
                    ((WeightedEdge) edge).weight = e.weight;
                    key = 1;
                }
            }
            if (key == 0) neighbors.get(e.u).add(e);
            return true;
        }
    }

    /**
     * 得到有权图的最小生成树
     */
    public MST getMinimumSpanningTree() {//默认节点
        return getMinimumSpanningTree(0);
    }

    public MST getMinimumSpanningTree(int startingVertex) {//指定节点

        //初始化
        List<Integer> T = new ArrayList<>();//已加入生成树的节点线性表
        int[] parent = new int[getSize()];
        for (int i = 0; i < parent.length; i++) parent[i] = -1;
        double totalWeight = 0;
        double[] cost = new double[getSize()];//每个节点的开销
        //注意：这里的开销指的是：这个顶点邻接到T中某个顶点具有的最小开销
        for (int i = 0; i < cost.length; i++) cost[i] = Double.POSITIVE_INFINITY;
        cost[startingVertex] = 0;

        //从T以外的节点向T加入新节点，贪婪算法，局部最优使得整体最优
        while (T.size() < getSize()) {
            double minimumCost = Double.POSITIVE_INFINITY;
            int u = -1;
            for (int i = 0; i < cost.length; i++) {   //找到不在T中且开销最小的节点
                if (!T.contains(i) && minimumCost > cost[i]) {
                    minimumCost = cost[i];
                    u = i;
                }
            }
            T.add(u);
            totalWeight += minimumCost;//将该节点移入T中
            // parent[u] = -1;

            for (Edge e : neighbors.get(u)) {//更新节点的开销和在最小生成树中的父节点
                if (cost[e.v] > ((WeightedEdge) e).weight) {
                    cost[e.v] = ((WeightedEdge) e).weight;
                    parent[e.v] = u;
                }
            }
        }

        return new MST(startingVertex, parent, T, totalWeight);
    }

    /**
     * 得到源到所有顶点的最短路径树
     * 贪婪算法和动态编程的结合
     */
    public ShortestPathTree getShortestPath() {
        return getShortestPath(0);
    }

    public ShortestPathTree getShortestPath(int sourceVertex) {
        //初始化
        List<Integer> T = new ArrayList<>();//已得到最短路径的节点
        int[] parent = new int[getSize()];
        for (int i = 0; i < parent.length; i++) parent[i] = -1;
        double[] cost = new double[getSize()];//源到每个节点的开销
        //注意：这里的开销指的是：这个顶点邻接到T中某个顶点，并具有到源顶点的最小开销
        for (int i = 0; i < cost.length; i++) cost[i] = Double.POSITIVE_INFINITY;
        cost[sourceVertex] = 0;

        //从T以外的节点向T加入新节点
        while (T.size() < getSize()) {
            double minimumCost = Double.POSITIVE_INFINITY;
            int u = -1;
            for (int i = 0; i < cost.length; i++) {   //找到不在T中且开销最小的节点
                if (!T.contains(i) && minimumCost > cost[i]) {
                    minimumCost = cost[i];
                    u = i;
                }
            }
            T.add(u);//将该节点移入T中

            for (Edge e : neighbors.get(u)) {//更新节点的开销和在最小生成树中的父节点
                if (cost[e.v] > cost[u] + ((WeightedEdge) e).weight) {
                    cost[e.v] = cost[u] + ((WeightedEdge) e).weight;
                    parent[e.v] = u;
                }
            }
        }

        return new ShortestPathTree(sourceVertex, parent, T, cost);
    }

    /**
     * 定义内部类：MST,
     * 继承自AbstractGraph.Tree
     * 用于描述最小生成树
     */
    public class MST extends Tree {
        private double totalWeight;

        public MST(int root, int[] parent, List<Integer> searchOrder, double totalWeight) {
            super(root, parent, searchOrder);
            this.totalWeight = totalWeight;
        }

        public double getTotalWeight() {
            return totalWeight;
        }
    }

    /**
     * 定义内部类：ShortestPathTree
     * 继承自AbstractGraph.Tree
     * 用于描述最短路径
     */
    public class ShortestPathTree extends Tree {
        private double[] cost;//存储从源到目的的开销

        public ShortestPathTree(int source, int[] parent, List<Integer> searchOrder, double[] cost) {
            super(source, parent, searchOrder);
            this.cost = cost;
        }

        //得到从源到目的的开销
        public double getCost(int v) {
            return cost[v];
        }

        //显示从源顶点开始的所有路径
        public void printAllPaths() {
            for (int i = 0; i < vertices.size(); i++) {
                printPath(i);//单条路径
                System.out.println("(cost: " + cost[i] + ")");
            }
        }
    }
}